package 中等.模拟;

/**
 * 索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到最大的集合
 * S并返回其大小，其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的规则。
 * 假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，
 * 4之后是A[A[A[i]]]... 以此类推，不断添加直到S出现重复的元素。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/array-nesting
 */
public class 数组嵌套_565 {

    public static void main(String[] args) {

        int[] nums = {5, 4, 0, 3, 1, 6, 2};
        System.out.println(new 数组嵌套_565().arrayNesting(nums));

    }

    /**
     * 每个节点入度和出度都是1，每个环互不相交，
     * 所以同一个环中不管以哪一个节点作为开头节点，结果一样，只需要遍历一次
     *
     * @param nums
     * @return
     */
    public int arrayNesting(int[] nums) {
        int max = 1;
        for (int i = 0; i < nums.length; i++) {
            int count = 0, curIdx = i;
            while (nums[curIdx] != -1) {
                count++;
                int tIdx = curIdx;
                curIdx = nums[curIdx];
                nums[tIdx] = -1;
            }
            max = Math.max(max, count);
        }
        return max;
    }

}
